#include <stdio.h>
#include <assert.h>

#include <deque>
#include <iostream>
#include <fstream>
#include <algorithm>

#include "contourtree.h"
#include "../math/timer.h"

using namespace PBVP;

ContourTree::ContourTree()
{
	m_MaxId = -1;
}

ContourTree::~ContourTree()
{}

void ContourTree::addNode(int id, float val) 
{
	nodes[id] = SuperNode(id, val);
}

void ContourTree::addNode(const CriticalPoint& cp)
{
	nodes[cp.id] = cp;
}

void ContourTree::addArc(int n, int m, int x1, int x2)
{
	SuperNode& node_n = nodes[n];
	SuperNode& node_m = nodes[m];

	node_n.addNeighbor(m, x1);
	node_m.addNeighbor(n, x2);
}

void ContourTree::reduce(void)
{
	SuperNodeMap::iterator it = nodes.begin();

	while (it != nodes.end())
	{
		SuperNode& node = (*it).second;
		int id = node.id;
		++it;
		if(node.degree() == 2) 
		{
			removeNode(id);
		}
	}
}

void ContourTree::print(void)
{
	int nd = (int)nodes.size();
	
	SuperNodeMap::iterator it = nodes.begin();
	while(it != nodes.end()) {
		SuperNode &node = (*it).second;
		printf("%d: ", node.id);
		for (int j = 0; j < node.degree(); j++)
		{
			printf("%d ", node.getNeighborAt(j));
		}
		printf("\n");
	}
}

void ContourTree::removeNode(int n)
{
	SuperNode& snode = nodes[n];

	// should never remove a node with degree > 2
#ifdef _DEBUG
	assert(snode.degree() <= 2);
#endif
	if (snode.degree() == 1)	// minimum or maximum point 
	{
		SuperNode& nei = nodes[snode.getNeighborAt(0)];
		nei.removeNeighbor(n);
	} else if (snode.degree() == 2) {
		int j = snode.getNeighborAt(0);
		int k = snode.getNeighborAt(1);
		SuperNode& node1 = nodes[j];
		SuperNode& node2 = nodes[k];

		int x1 = node1.getNeighborTag(n);
		int x2 = node2.getNeighborTag(n);
		node1.removeNeighbor(n);
		node2.removeNeighbor(n);
		addArc(j, k, x1, x2);
	}
	nodes.erase(n);
}

bool ContourTree::isLeaf(int n)
{
	SuperNode& node = nodes[n];
	return ( node.degree() == 1 && node.id != m_MaxId );
}

ContourTree* ContourTree::mergeTree(ContourTree* joinTree, ContourTree* splitTree)
{
	printf("start merging join and split trees...\n");
	Timer timer;
	ContourTree* conTree = new ContourTree();

	std::deque<LeafNode> leafs;
	// iterate through the join tree
	printf("add nodes to the merged tree\n");
	SuperNodeMap::iterator it = joinTree->nodes.begin();
	while(it != joinTree->nodes.end())
	{
		SuperNode& joinNode = (*it).second;
		conTree->addNode(joinNode);
		int id = joinNode.id;
		SuperNode& splitNode = splitTree->getNode(id);		// The same node in split tree
		if(joinTree->isLeaf(id) && splitNode.degree() <= 2)
		{
			LeafNode leaf(id, 0);
			leafs.push_back(leaf);
		} else if (splitTree->isLeaf(id) && joinNode.degree() <= 2)
		{
			LeafNode leaf(id, 1);
			leafs.push_back(leaf);
		}
		++it;
	}
	
	// remove nodes from join and split trees, and add superarcs to the merged tree.
	printf("add super arcs to the merged tree\n");
	while(!leafs.empty()) {
		int id, nid;
		SuperNode *pNode;
		LeafNode leaf = leafs.front();
		leafs.pop_front();
		id = leaf.id;
		switch(leaf.type) {
		case 0:
			pNode = &(joinTree->getNode(id));			
			break;
		case 1:
			pNode = &(splitTree->getNode(id));
			break;
		}

		int degree = pNode->degree();
		if(degree > 0) { // not the last node in the tree
			nid = pNode->getNeighborAt(0);
			int x1, x2;
			switch(leaf.type) {
			case 0:
				{
					SuperNode &tmp = joinTree->getNode(nid);
					x2 = tmp.getNeighborTag(id);
				}
				break;
			case 1:
				{
					SuperNode &tmp = splitTree->getNode(nid);
					x2 = tmp.getNeighborTag(id);
				}
				break;
			}
			x1 = pNode->getTagAt(0);
#ifdef _DEBUG
			//printf("add arc (%d %d) ", id, nid);
			//printf("%d, %d \n", leaf.type, p_stree->getNode(26552));
			//fflush(stdout);
#endif
			conTree->addArc(id, nid, x1, x2);
		}
		joinTree->removeNode(id);
		splitTree->removeNode(id);

		if(degree > 0) {
			switch(leaf.type) {
			case 0:
				if(joinTree->isLeaf(nid) && splitTree->getNode(nid).degree() <= 2) {
					LeafNode leaf(nid, 0);
					leafs.push_back(leaf);
				} else if(splitTree->isLeaf(nid) && joinTree->getNode(nid).degree() <=2) {
					LeafNode leaf(nid, 1);
					leafs.push_back(leaf);
				}
				break;
			case 1:
				if(splitTree->isLeaf(nid) && joinTree->getNode(nid).degree() <= 2) {
					LeafNode leaf(nid, 1);
					leafs.push_back(leaf);
				} else if(joinTree->isLeaf(nid) && splitTree->getNode(nid).degree() <=2) {
					LeafNode leaf(nid, 0);
					leafs.push_back(leaf);
				}
				break;
			}
		}
	}
		
	conTree->setMaxID(std::max(joinTree->getMaxID(), splitTree->getMaxID()));
	return conTree;
}

bool ContourTree::saveFile(const char* fname)
{
	std::ofstream out(fname);
	out << 0 << std::endl;
	SuperNodeMap::iterator it = nodes.begin();
	
	while (it != nodes.end()) 
	{
		SuperNode& node = (*it).second;
		out << node.id << " " << node.val << " ";
		out << node.degree() << " ";
		for(int i = 0; i < node.degree(); i++) {
			out << node.getNeighborAt(i) << " ";
		}
		out << std::endl;
		++it;
	}
	out.close();
	return true;
}

bool ContourTree::loadFile(const char* fname)
{
	std::ifstream in(fname);
	int head;
	in >> head;
	if (head != 0){
		return false;
	}

	while(!in.eof()) {
		int id, nid, degree;
		float val;
		in >> id;
		if(in.eof()) break;
		in >> val;
		in >> degree;
		
		addNode(id, val);
		for(int i = 0; i < degree; i++) {
			in >> nid;
			nodes[id].addNeighbor(nid);
		}
	}
	in.close();
	return true;
}

void ContourTree::truncateLower(float x)
{
	// traverse every node in contour tree incrementally, 
	// delete the node if its value and the values of all its neighbors 
	// are below x
	std::vector<CriticalPoint>* pCPVector = getSortedPoints();
	std::vector<CriticalPoint>::iterator it = pCPVector->begin();
	while(it != pCPVector->end()) {
		int id = (*it).id;
		float val = (*it).val;
		if(val >= x) break;		// done
		bool truncFlag = true;
		SuperNode& node = nodes[id];
		for(int i = 0; i < node.degree(); i++) {
			SuperNode& nei = nodes[node.getNeighborAt(i)];
			if(nei.val > x) { // node connects to a node with value > x
				truncFlag = false;
				break;
			}
		}
		if( truncFlag && nodes[id].degree() <= 2) {
			removeNode(id);
		}

	}
	delete pCPVector;
}